import java.math.BigInteger;

/*****************************************************
 *
 * Mathematische Grundlage
 * http://www.markdiamond.com.au/download/joous-3-1-1.pdf solutions: The
 * smallest numbers having multiplicative persistences of 1, 2, ... are 10, 25,
 * 39, 77, 679, 6788, 68889, 2677889, 26888999, 3778888999, 277777788888899
 *
 * Gemessene Zeite auf Gruenau 600ms, auf Rabe 900ms
 *
 * History: v1: Schleifen. Rang 10 in 6 Minuten, 11 in ... irgendwann
 *
 * v2: Versuch der Konvertierung des Src auf Primfaktorenkalkulation inkl
 * Optimierung
 *
 * v3: vollstaendiger Neuanfang, Erkenntnis, das viele Optimierungen beim
 * Primansatz ueberfluessig sind.
 *
 *
 ***************************************************/

public class Quer {

	public static void outp(String l, long[] p, String r) {
		System.out.print(l + ": ");
		for (int i = 1; i < 10; i++) {
			System.out.print(p[i] + " ");
		}
		System.out.print(" " + r);
	}

	public static void outs(String l) {
		System.out.print(l);
	}

	public static long[] zuweisen(long v1, long v2, long v3, long v4, long v5, long v6, long v7, long v8, long v9) {
		long[] result = { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L };

		result[0] = 0L;
		result[1] = v1;
		result[2] = v2;
		result[3] = v3;
		result[4] = v4;
		result[5] = v5;
		result[6] = v6;
		result[7] = v7;
		result[8] = v8;
		result[9] = v9;

		return result;
	}

	public static String stringmultiply(int count, String with) {
		return new String(new char[count]).replace("\0", with);
	}

	public static BigInteger concat(long[] p) {

		BigInteger result = BigInteger.valueOf(0);
		String dummy = "";
		// String dummychar ="";

		for (int i = 1; i < 10; i++) {
			if (p[i] > 0) {
				// dummychar = ""+i;

				// dummy = dummy + stringmultiply((int)p[i], dummychar);

				for (int k = 0; k < p[i]; k++) {
					dummy = dummy + i;
				}
			}
		}

		if (dummy.equals("") == false) {
			result = result.add(new BigInteger(dummy));
		}

		return result;
	}

	public static long[] shorten(long[] p) {
		long[] result = { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L };
		long d = 0L;

		result = p;

		// outp(" Start:", result, "");
		d = result[2] / 3;
		result[8] = result[8] + d;
		result[2] = result[2] - (3 * d);
		// outp(" 3*2->8:", result, "");
		d = result[3] / 2;
		result[9] = result[9] + d;
		result[3] = result[3] - (2 * d);
		// outp(" 2*3->9:", result, "");
		d = Math.min(result[2], result[3]);
		result[6] = result[6] + d;
		result[2] = result[2] - d;
		result[3] = result[3] - d;
		// outp(" 2*3->6:", result, "");
		d = (result[2] / 2);
		result[4] = result[4] + d;
		result[2] = result[2] - (2 * d);
		// outp(" 2*2->4:", result, "");
		return result;
	}

	public static int mp(BigInteger zahl) {
		int grad = 0;
		BigInteger z = zahl;
		BigInteger produkt, BigNull = BigInteger.valueOf(0);
		BigInteger[] divider = new BigInteger[2];
		BigInteger BigTen = BigInteger.valueOf(10);

		// outs(" z:" + z);
		do {
			produkt = BigInteger.valueOf(1);
			grad++;
			while (z.compareTo(BigNull) != 0) {
				divider = z.divideAndRemainder(BigTen);
				produkt = produkt.multiply(divider[1]);
				z = divider[0];
			}
			z = produkt;
		} while (z.compareTo(BigTen) >= 0);
		return grad;
	}

	public static void main(String[] args) {

		int Kmax = Integer.parseInt(args[0]); // argumentenuebername
		if ((Kmax > 11) | (Kmax < 1)) {
			outs("ERROR: Quer n   with 0<n<12 \nEXIT");
			System.exit(1);
		}
		int MaxExp = 19; // max 19

		int qpgrad = 0;

		long[] exponent = { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L };

		BigInteger zahl, BigNull = BigInteger.valueOf(0);
		BigInteger[] resultat = new BigInteger[12];

		for (int i = 0; i < 12; i++) {
			resultat[i] = resultat[i].valueOf(0);
		}

		// long startZeit = System.currentTimeMillis(); // stopuhr

		for (int p7 = 0; p7 <= MaxExp; p7++) {
			for (int p3 = 0; p3 <= MaxExp; p3++) {
				for (int p2 = 0; p2 <= MaxExp; p2++) {
					if (p2 < 2) {
						for (int p5 = 0; p5 <= MaxExp; p5++) {

							exponent = zuweisen(0L, p2, p3, 0L, p5, 0L, p7, 0L, 0L);
							// outp("Exponenten", exponent, "");

							exponent = shorten(exponent);
							// outp("Reduziert", exponent, "");

							zahl = concat(exponent);
							// outs(" Zahl:" + zahl);

							qpgrad = mp(zahl);
							// outs(" MP:" + qpgrad);

							if ((resultat[qpgrad].compareTo(BigNull) == 0) | (resultat[qpgrad].compareTo(zahl) > 0)) {
								resultat[qpgrad] = zahl;
								// outs(" NEW ");
							}

							// outs("\n");

							// outp("Faktoren", faktoren, "\n");
						}
					} else {
						exponent = zuweisen(0L, p2, p3, 0L, 0L, 0L, p7, 0L, 0L);
						// outp("Exponenten", exponent, "");

						exponent = shorten(exponent);
						// outp("Reduziert", exponent, "");

						zahl = concat(exponent);
						// outs(" Zahl:" + zahl);

						qpgrad = mp(zahl);
						// outs(" MP:" + qpgrad);

						if ((resultat[qpgrad].compareTo(BigNull) == 0) | (resultat[qpgrad].compareTo(zahl) > 0)) {
							resultat[qpgrad] = zahl;
							// outs(" NEW ");
						}

					}
				}
			}
		}
		
		for (int k = 2; k <= Kmax; k++) { // schleife k durchzaehlen bis kmax
			System.out.println(k + " Schritte: " + resultat[k]);
		}
		// System.out.println(" Zeit:" + ((System.currentTimeMillis() -
		// startZeit)));

	}
}